package com.lry.basic.algorithm.common;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树的广度优先遍历 | 时间限制：1秒 | 内存限制：262144K | 语言限制：不限
 * 有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。现有两组字母，分别表示后序遍历（左孩子->右孩子->父节点）和中序遍历（左孩子->父节点->右孩子）的结果，请输出层次遍历的结果。
 * 输入描述:
 * 输入为两个字符串，分别是二叉树的后续遍历和中序遍历结果。
 * 输出描述:
 * 输出二叉树的层次遍历结果。
 *
 * 示例1
 * 输入
 * CBEFDA CBAEDF
 * 输出
 * ABDCEF
 * 说明
 * 二叉树为：
 *     A
 *    / \
 *   B   D
 *  /   / \
 * C   E   F
 * /\
 *1  2
 *
 * 12cbefda
 * 1c2baedf
 */
public class BuildTree {


    public static void main(String[] args) {
        BuildTree buildTree = new BuildTree();

        Node node = buildTree.buildTree("12cbefda", "1c2baedf");

        buildTree.levelOrder(node);
    }

    private void levelOrder(Node root){
        if(null==root){
            return;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            Node node = queue.poll();
            System.out.print(node.data);

            if(null!=node.left){
                queue.add(node.left);
            }
            if(null!=node.right){
                queue.add(node.right);
            }
        }

    }

    private Node buildTree(String post,String in){
        if(post.length()<=0 || in.length()<=0){
            return null;
        }
        char c = post.charAt(post.length() - 1);
        Node node = new Node(c);

        int i = in.indexOf(c);

        node.left = buildTree(post.substring(0,i),in.substring(0,i));
        node.right = buildTree(post.substring(i,post.length()-1),in.substring(i+1,post.length()));
        return node;
    }


    class Node{
        public char data;
        public Node left;
        public Node right;

        public Node(char c){
            this.data = c;
        }
    }

}

